package com.leetcode.蓝桥杯.十二届国赛;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class 编程题8 {

	public static void main(String[] args) {
		/**
		 * 以下做法是：按价格排序，每天吃一个，并时刻更新每个糖果的剩余时间，这个糖果吃完，再吃下一个。
		 * 但这种方法是错的。假设要吃10天，然后有三个巧克力的价格、剩余天数、数量分别是：{1 10 5} {2 3 10} {3 10 10}
		 * 按照这个方法，前5天是吃价格为1的巧克力，后5天只能吃价格为3的巧克力
		 * 但是，我们发现：前3天可以先吃价格为2的，接下来5天吃价格为1的，剩下2天吃价格为3的，这样的花费更少
		 */
//		Scanner input = new Scanner(System.in);
//		int x = input.nextInt();
//		int n = input.nextInt();
//		Chocolate[] c = new Chocolate[n];
//		for (int i = 0; i < n; i++) {
//			c[i] = new Chocolate();
//			c[i].price = input.nextInt();
//			c[i].date = input.nextInt();
//			c[i].num = input.nextInt();
//		}
//		long res = 0;// 用了多少钱
//		sort(c);
//		int day = 0;// 表示当前过了多少天
//		boolean flag = true;
//		for (int i = 0; i < n; i++) {
//			c[i].date -= day;// 更新，这个巧克力还有多少钱过期
//			int surplus = x - day;//剩余多少天
//			if (c[i].date > 0) {
//				int num = Math.min(c[i].date, c[i].num);//表示当前可以买多少颗巧克力
//				if(num > surplus) num = surplus;//如果能购买的数量大于剩余天数，则只需要买剩余天数的数量即可
//				res += c[i].price * num;
//				day += num;
//				if (day >= x) {
//					System.out.println(res);
//					flag = false;
//					break;
//				}
//			}
//		}
//		if (flag)
//			System.out.println(-1);
//		input.close();
		
		InputReader input = new InputReader();
		int x = input.nextInt();
		int n = input.nextInt();
		Chocolate[] c = new Chocolate[n];
		for (int i = 0; i < n; i++) {
			c[i] = new Chocolate();
			c[i].price = input.nextInt();
			c[i].date = input.nextInt();
			c[i].num = input.nextInt();
		}
		long res = 0;// 用了多少钱
		//自定义排序
		sort(c);
		//把最开始的每一天就加入集合中
		TreeSet<Integer> set = new TreeSet<>();
		for(int i = 1;i <= x;i++) {
			set.add(i);
		}
		int p = 0;//表示当前是第几中巧克力，从0开始
		//set.size() != 0 表示还有日期没有吃巧克力
		//p < n 表示巧克力还没有遍历完
		while(set.size() != 0 && p < n) {
			//c[p].num != 0 表示这个巧克力还有存货
			//set.size() != 0 表示还有天数没有吃巧克力
			//set.first() <= c[p].date 集合中最小的日期小于保质期，说明当前这个巧克力可以吃
			while(c[p].num != 0 && set.size() != 0 && set.first() <= c[p].date) {
				res += c[p].price;
				c[p].num --;//数量减1
				Integer it = set.lower(c[p].date + 1);//找到小于等于c[p].date的日期，来吃当前这个巧克力c[p]
				//因为lower(T ele)方法,找的是严格小于ele的元素
				set.remove(it);
			}
			p++;//下一种巧克力
		}
		//还有日期没有吃巧克力
		if(set.size() != 0)
			System.out.println(-1);
		else 
			System.out.println(res);
	}

	/**
	 * 按价格排序，价格一样，就排过期的天数，天数小的放前边
	 * @param c
	 */
	static void sort(Chocolate[] c) {
		Arrays.sort(c, (a, b) -> {
			if(a.price == b.price) {
				return Integer.compare(a.date,b.date);
			}
			return Integer.compare(a.price, b.price);
		});
	}
}

class Chocolate {
	int price;
	int date;
	int num;
}

class InputReader {
    BufferedReader buf;
    StringTokenizer tok;

    InputReader() {
        buf = new BufferedReader(new InputStreamReader(System.in));
    }

    boolean hasNext() {
        while (tok == null || !tok.hasMoreElements()) {
            try {
                tok = new StringTokenizer(buf.readLine());
            } catch (Exception e) {
                return false;
            }
        }
        return true;
    }

    String next() {
        if (hasNext()) return tok.nextToken();
        return null;
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }
}
